import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class TestBinaryTree {
    static class TreeNode{
        public char value;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(char value) {
            this.value = value;
        }
    }
    public TreeNode creatTree1() {
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');

        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        E.right = H;
        return A;
    }

    public  int i;
    public   TreeNode creatTree2(String str){//输入一串字符串创建一个二叉树
        char ch=str.charAt(i);
        TreeNode node=null;
        if(ch!='#'){
            i++;
            node=new TreeNode(ch);
            node.left=creatTree2(str);
            node.right=creatTree2(str);
        }else i++;

        return node;
    }

    public static int size;
    public static int leafNodeCount;

    public void size1(TreeNode root){
        if (root==null) return ;
        size++;
        size1(root.left);
        size1(root.right);
    }

    public int  size2(TreeNode root){
        if (root==null) return 0;
        int num=0;
        num+=size2(root.left);
        num+=size2(root.right);
        return num+1;
    }

    public void getLeafNodeCount1(TreeNode root){
        if (root==null) return;
        if (root.left==null&&root.right==null){
            leafNodeCount++;
            return;
        }
        getLeafNodeCount1(root.left);
        getLeafNodeCount1(root.right);
    }

    public int getLeafNodeCount2(TreeNode root){
        if (root==null) return 0;
        if (root.left==null&&root.right==null){
            return 1;
        }
        return getLeafNodeCount2(root.left)+getLeafNodeCount2(root.right);

    }


    public List<Character> preorderTraversal(TreeNode root) {
        List<Character> list =new ArrayList<>();
        if (root==null) return list;
        list.add(root.value);
        list.addAll(preorderTraversal(root.left));
        list.addAll(preorderTraversal(root.right));
        return list;
    }

    public int getKLevelNodeCount(TreeNode root,int k){
        if (root==null) return 0;
        if (k==1){
            return 1;
        }
        return  getKLevelNodeCount(root.left,k-1) +
                getKLevelNodeCount(root.right,k-1);
    }

    public TreeNode findVal(TreeNode root,int val){
        TreeNode alm=null;
        if (root==null) return null;
        if (alm.value==val) return root;

        alm=findVal(root.left,val);
        if (alm!=null) return root;

        alm=findVal(root.right,val);
        if (alm!=null) return root;

        return null;
    }

    public int treeHight(TreeNode root){//树的高度
        if(root==null) return 0;
        int num1=1;
        int num2=1;
        num1+=treeHight(root.left);
        num2+=treeHight(root.right);
        return num1>num2?num1:num2;
    }

    public TreeNode invertTree(TreeNode root) {//反转二叉树
        if(root==null) return root;
        TreeNode rt=root.left;
        root.left=root.right;
        root.right=rt;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }

    public boolean isSameTree(TreeNode p, TreeNode q) {//检查两颗二叉树是否相同
        if(p==null&&q==null) return true;
        if((p!=null&&q==null)||(p==null&&q!=null)) return false;
        if(p.value==q.value)
            return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
        return false;
    }

    public boolean isSymmetric(TreeNode root) {//对称二叉树
        if(root==null) return true;
        return isSameTree(root.left,root.right);
    }

    public boolean isSubtree(TreeNode root, TreeNode subRoot) {//另一棵树的子树
        if(isSameTree(root,subRoot)==true)
            return true;
        if(root==null||subRoot==null) return false;
        return isSubtree(root.left,subRoot)||isSubtree(root.right,subRoot);
    }

    public boolean isBalanced1(TreeNode root) {//法一：判断是否是平衡二叉树（时间复杂度为O（n^2））
        if(root==null) return true;
        int leftTree=treeHight(root.left);
        int rightTree=treeHight(root.right);
        return Math.abs(leftTree-rightTree)<=1&&isBalanced1(root.left)&&isBalanced1(root.right);
    }

    public boolean isBalanced2(TreeNode root) {//法二：时间复杂度：O（n）
        if(root==null) return true;
        if(treeHight2(root)==-1) return false;
        return true;
    }

    public int treeHight2(TreeNode root){
        if(root==null) return 0;
        int hight1=treeHight2(root.left);
        int hight2=treeHight2(root.right);
        if(hight1<0||hight2<0) return -1;
        if(Math.abs(hight1-hight2)<=1)
            return (hight1>hight2?hight1:hight2)+1;
        return -1;
    }

    public boolean levelOrder(TreeNode root){
        if(root==null) return false;
        Queue<TreeNode> queue =new LinkedList<>();
        queue.offer(root);
        TreeNode cur=root;

        while(cur!=null){
            cur=queue.poll();
            if (cur==null) break;
            queue.offer(cur.left);
            queue.offer(cur.right);
        }

        while(queue.size()!=0){
            if (queue.poll()!=null) return false;
        }
        return true;
    }
}